package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0324_01 {

    /**
     * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
     *
     *
     *
     * 示例 1:
     *
     * 输入: [10,2]
     * 输出: "102"
     * 示例 2:
     *
     * 输入: [3,30,34,5,9]
     * 输出: "3033459"
     *
     *
     * 提示:
     *
     * 0 < nums.length <= 100
     * 说明:
     *
     * 输出结果可能非常大，所以你需要返回一个字符串而不是整数
     * 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
     *
     * 思路分析：本题求凭借起来的最小数字，本质上是一个排序问题，数组nums中的任意两个数字的字符串为 x 和 y
     * 则规定  排序判断规则为
     * 若凭借字符串  x+y > y+x 则 x “大于” y
     * 反之，若 x+y < y+x 则 x “小于” y  eg x=2 y=10 此处的小于代表，排序完成后，数组中的x应该在y的左边
     * 根据以上规则，套用任何排序方法对 nums 执行排序即可
     *
     * 算法流程：
     * 1、初始化：字符串列表 strs，保存各数字的字符串格式
     * 2、列表排序：应用以上排序判断规则，对strs执行排序
     * 3、返回值：凭借strs中的所有字符串，并返回
     *
     * 本题中采取 快速排序 和 内置函数两种排序方法
     * @param nums
     * @return
     */
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs,(x,y) -> (x+y).compareTo(y+x));
        StringBuffer res = new StringBuffer();
        for (String str : strs) {
            res.append(str);
        }
        return res.toString();
    }


//    public String minNumber(int[] nums) {
//        String[] strs = new String[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            strs[i] = String.valueOf(nums[i]);
//        }
//        quickSort(strs, 0, strs.length - 1);
//        StringBuilder res = new StringBuilder();
//        for (String s : strs)
//            res.append(s);
//        return res.toString();
//    }

    public void quickSort(String[] strs, int low, int high) {
        if (low < high) {
            int middle = getMiddle(strs, low, high);
            quickSort(strs, low, middle - 1);
            quickSort(strs, middle + 1, high);
        }
    }

    public int getMiddle(String[] strs, int low, int high) {
        //数组的第一个数为基准元素
        String temp = strs[low];
        while (low < high) {
            //从后向前找比基准小的数
            while (low < high && (strs[high] + temp).compareTo(temp + strs[high]) >= 0)
                high--;
            //把比基准小的数移到低端
            strs[low] = strs[high];
            //从前向后找比基准大的数
            while (low < high && (strs[low] + temp).compareTo(temp + strs[low]) <= 0)
                low++;
            //把比基准大的数移到高端
            strs[high] = strs[low];
        }
        strs[low] = temp;
        return low;
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
